package com.xypower.any;

import java.util.PriorityQueue;

/**
 * 一块金条切成两半，是需要花费和长度数值一样的铜板的。
 * 比如长度为20的金条，不管切成长度 多大的两半，都要花费20个铜板。
 * 一群人想整分整块金条，怎么分最省铜板
 */
public class LessMoneySplitGold {
    public static int lessMoney(int[] arr){
        PriorityQueue<Integer> pQ = new PriorityQueue<>();
        for (int i = 0;i < arr.length;i++){
            pQ.add(arr[i]);
        }
        int sum = 0;
        int cur = 0;
        //每次结合的数字扔回小根堆，累加所有代价
        while (pQ.size() > 1){
            cur = pQ.poll() + pQ.poll();
            sum += cur;
            pQ.add(cur);
        }
        return sum;
    }

    public static class MinheapComparator implements Comparable<Integer>{

        @Override
        public int compareTo(Integer o) {
            return 0;
        }
    }
}
